1. Technical Field
The present invention relates in general to a system and method for providing memory coherence in a multiprocessor system. In particular, the present invention uses cache line access frequencies to determine when to switch from an invalidation protocol to an update protocol.
2. Description of the Related Art
Cache, or memory, coherence protocols are used in shared memory systems, such as symmetric multiprocessor systems (SMPs), to enable efficient program execution. In such systems, multiple copies of data may exist, for example, in multiple private caches associated with the processors. Each processor in the system may have its own private cache, with the private caches kept coherent with each other. In order to maintain memory coherency between the multiple private caches in an SMP system, a cache coherence protocol is used. Two prior art cache coherence protocols that are used are the Invalidation Protocol and the Update Protocol.
FIG. 1 is a block diagram that depicts a prior art invalidation protocol. Central processing unit (CPU) 105 includes cache manager 110 for controlling access to cache 115. Cache 115 is a private cache used by CPU 105. Similarly, CPU 125 includes cache manager 130 for controlling access to cache 135. Cache 135 is a private cache associated with CPU 125. Cache 115 and cache 135 are kept coherent with each other through the use of an invalidation protocol. CPU 105 and CPU 125 are connected to each other, and to shared memory 140, via bus 120. When CPU 105 writes data to cache 115, all remote copies of the specific cache line (or lines) are invalidated. For example, cache manager 110 writes a line of data to cache line 145 in cache 115. Validation bit 150 is set to “Y” to indicate that the data in cache line 145 is valid. Then, cache manager 110 sends an invalidate signal on bus 120 that tells all other cache managers to invalidate their copy of the cache line. Cache manager 130 receives the invalidate signal from bus 120 and invalidates cache line 155 in its private cache 135. Validation bit 160 is set to “N” to indicate that cache line 155 is not valid.
One problem with the prior art invalidation protocol is that there are situations where the modify requestor (for example, CPU 105 in FIG. 1) is not the process or CPU that most frequently accesses the line. In such instances, cache misses may occur to the private caches of a process or CPU that more frequently accesses the line. For example, CPU 125 will get a cache miss if it attempts to access line 155.
FIG. 2 is a block diagram that depicts a prior art update protocol. CPU 205 includes cache manager 210 for controlling access to cache 215. Cache 215 is a private cache used by CPU 205. Similarly, CPU 225 includes cache manager 230 for controlling access to cache 235. Cache 235 is a private cache associated with CPU 225. Cache 215 and cache 235 are kept coherent with each other through the use of an update protocol. CPU 205 and CPU 225 are connected to each other, and to shared memory 240, via bus 220. When CPU 205 writes data to cache 215, the modified data is broadcast on bus 220 so that other caches with copies of the data can obtain a copy of the modified data. For example, cache manager 210 writes a line of data to cache line 245 in cache 215. Cache manager 210 then broadcasts the updated line by sending the modified data on bus 220. Because CPU 225 has a copy of the particular cache line in its private cache 235, it obtains a copy of the modified data. Cache manager 230 receives the updated data from bus 220, and writes the data to cache line 255 in cache 235.
While the update protocol results in fewer cache misses than the invalidation protocol, it is inefficient, as not every process or CPU will need to keep the modified data in their private cache.
What is needed, therefore, is a system and method for efficient memory coherence in a multiprocessor system.